/*
628. 三个数的最大乘积

给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例 1:

输入: [1,2,3]
输出: 6

示例 2:

输入: [1,2,3,4]
输出: 24

注意:

    给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。
    输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。
*/

/*
1:取得最大的3个正数(非负数)和最小的两个负数
2:负数数量大于等于两个时,比较负数的积和2,3位正数的积
3:取较大者
4:全是负数的时候...
*/
class Solution
{
public:
    int maximumProduct(vector<int> &nums)
    {
        // if (nums.size() < 3)
        if(nums.size() == 3) return nums[1] * nums[2] * nums[0];
        int mx[3] = {-2147483648, -2147483648, -2147483648};
        int mn[2] = {0, 0};

        for(int x : nums) {
            if(x > mx[0]) {
                mx[2] = mx[1];
                mx[1] = mx[0];
                mx[0] = x;
            } else if(x > mx[1]) {
                mx[2] = mx[1];
                mx[1] = x;
            } else if(x > mx[2]) {
                mx[2] = x;
            }
            if(x < 0) {
                if(x < mn[0]) {
                    mn[1] = mn[0];
                    mn[0] = x;
                } else if(x < mn[1]) {
                    mn[1] = x;
                }
            }
        }
        if(mx[0] <= 0) {
            /* all negative */
            return mx[0] * mx[1] * mx[2];
        }
        if(mx[2] < 0) {
            /* count(negative) >= 2 && count(non-negative) < 3 */
            return mx[0] * mn[0] * mn[1];
        }
        return mx[0] * max(mn[0] * mn[1], mx[1] * mx[2]);
    }
};